package org.example.binarysearch;

/**
 * @author wujiale
 */
public class BinarySearch {
    /**
     * 二分查找基础版
     * Params： a-待查找的升序数组
     *         target -待查找的目标值
     * Returns 找到返回索引
     *         找不到返回 -1
      */
    public static void main(String[] args) {
        int[] a = {7,11,12,14,23,25,35,35,35,35,47,88,90};
        /*System.out.println("查找到元素索引为..."+binarySearchBasic(a, 14));
        System.out.println("查找到元素索引为..."+binarySearchBasic(a, 15));
        System.out.println("查找到元素索引为..."+binarySearchBasic(a, 90));

        System.out.println("查找到元素索引为..."+binarySearchAlternative(a, 14));
        System.out.println("查找到元素索引为..."+binarySearchAlternative(a, 15));
        System.out.println("查找到元素索引为..."+binarySearchAlternative(a, 90));*/

        System.out.println("leftmost查找到元素索引为..."+binarySearchLeftmost(a, 35));

        System.out.println("rightmost查找到元素索引为..."+binarySearchRightmost(a, 35));
        System.out.println("rightmost查找到元素索引为..."+binarySearchRightmost1(a, 35));

    }

    public static int binarySearchBasic(int[] a,int target){
        //1.确定两个指针 i j
        int i = 0,j = a.length -1;
        //循环比较中间值和目标的大小 循环结束的条件是头指针i大于尾指针j
        //范围内有东西
        while (i <= j){
            //中间索引 java自动取整 其他语言需要调用 floor()
            int m = ( i + j ) >>> 1;
            //比较中间值与目标
            if( target < a[m] ){
                //尾指针指向中间索引-1
                j = m -1;
            }else if (a[m] < target){
                //头指针指向 m + 1
                i = m + 1;
            } else{
                return m;
            }
        }
        return -1;
    }


    public static int binarySearchAlternative(int[] a,int target){
        int i = 0,j = a.length;      //改动1 j指向一个并不存在的元素 j指向的一定不是查找的元素
        while (i < j){               //改动2 j指向的元素不参与比较
            int m = ( i + j ) >>> 1;
            if( target < a[m] ){
                j = m;               //改动3
            }else if (a[m] < target){
                i = m + 1;
            } else{
                return m;
            }
        }
        return -1;
    }

    /**
     * 二分查找优化版二分查找改进版
     * 改进点：
     * 查找第一次出现的元素索引
     *
     * @param a
     * @param target
     * @return
     */
    public static int binarySearchLeftmost(int[] a,int target){
        int i = 0,j = a.length -1 ;
        int candidate = -1;
        while (i < j){
            int m = ( i + j ) >>> 1;
            if( target < a[m] ){
                j = m - 1;               //改动3
            }else if (a[m] < target){
                i = m + 1;
            } else{
                //记录m的索引 关键！！ 当值相等时 j=m-1 将右指针向左移动
                candidate = m;
                j = m - 1;
            }
        }
        return candidate;
    }

    /**
     * 查找最后一次出现的元素索引
     * @param a
     * @param target
     * @return
     */
    public static int binarySearchRightmost(int[] a, int target) {
        int i = 0, j = a.length - 1;
        int candidate = -1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                candidate = m;   // 记录候选位置
                i = m + 1;       // 继续向右
            }
        }
        return candidate;
    }

    /**
     * 查找最后一次出现的元素索引
     * @param a
     * @param target
     * @return
     */
    public static int binarySearchRightmost1(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i < j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            }else {
                //target小于中间值时继续向右移动指针查找
                i = m + 1;
            }
        }
        return i - 1;
    }
}
